#include "BinaryTree.h"
#include <iostream>

// 无参构造
BinaryTree::BinaryTree()
{
    root = nullptr;
}

// 析构
BinaryTree::~BinaryTree()
{
    FreeNode(root);
}

// 插入
void BinaryTree::Insert(const ElementType &element)
{
    root = InsertNode(root, element);
}

// show
void BinaryTree::show()
{
    std::cout<<"前:";
    PrevTravel(root);
    std::cout<<std::endl;

    std::cout<<"中:";
    MidTravel(root);
    std::cout<<std::endl;

    std::cout<<"后:";
    PostTravel(root);
    std::cout<<std::endl;
}

// 找节点
ElementType *BinaryTree::FindElement(const ElementType &element)
{
    return FindNode(root, element);
}

// 删除节点
void BinaryTree::RemoveByElement(const ElementType &element)
{
    root = RemoveNode(root, element);
}

// 插入（递归）
BinaryTree::TreeNode *BinaryTree::InsertNode(TreeNode *node, const ElementType &element)
{
    // 递归终止条件
    if(node == nullptr)
        return new TreeNode(element);
    // 数据已经存在
    if(node->value == element)
        return node;
    if(node->value > element)
    {
        // 递归插入左子树
        node->left = InsertNode(node->left, element);
        // 左边重 失衡
        if(LRDvtion(node) > 1)
        {
            // 左左失衡
            if(element < node->left->value)
            {
                node = RotateRight(node);
            }
            // 左右失衡
            else
            {
                node = RotateLeftRight(node);
            }
        }
    }
    else
    {
        // 递归插入右子树
        node->right = InsertNode(node->right, element);
        // 右边重 失衡
        if(LRDvtion(node) < -1)
        {
            // 右右失衡
            if(element > node->right->value)
            {
                node = RotateLeft(node);
            }
            // 右左旋
            else
            {
                node = RotateRightLeft(node);
            }
        }
    }
    return node;
}

// 前序遍历
void BinaryTree::PrevTravel(TreeNode *node)
{
    if(node == nullptr)
        return;
    std::cout<<node->value<<" ";
    PrevTravel(node->left);
    PrevTravel(node->right);
}

// 中序遍历
void BinaryTree::MidTravel(TreeNode *node)
{
    if(node == nullptr)
        return;
    MidTravel(node->left);
    std::cout<<node->value<<" ";
    MidTravel(node->right);
}

// 后序遍历
void BinaryTree::PostTravel(TreeNode *node)
{
    if(node == nullptr)
        return;
    PostTravel(node->left);
    PostTravel(node->right);
    std::cout<<node->value<<" ";
}

// 释放（递归）
void BinaryTree::FreeNode(TreeNode *node)
{
    if(node == nullptr)
        return;
    FreeNode(node->left);
    FreeNode(node->right);
    delete node;
}

// 找节点
ElementType *BinaryTree::FindNode(TreeNode *node, const ElementType &element)
{
    if(node == nullptr)
        return nullptr;
    
    if(node->value == element)
        return &node->value;
    if(node->value < element)
        return FindNode(node->right, element);
    if(node->value > element)
        return FindNode(node->left, element);
    return nullptr;  
 
}

// 删除节点
BinaryTree::TreeNode *BinaryTree::RemoveNode(TreeNode *node, const ElementType &element)
{
    if(node == nullptr)
        return nullptr;
    if(node->value < element)
    {
        node->right = RemoveNode(node->right, element);
    }
    else if(node->value > element)
    {
        node->left = RemoveNode(node->left, element);
    }
    else
    {
        // 叶子
        if(node->left == nullptr && node->right == nullptr)
        {
            delete node;
            return nullptr;
        }
        // 左右孩子都存在
        else if(node->left != nullptr && node->right != nullptr)
        {
            // 取右子树中最小的节点
            TreeNode *min = GetMinNode(node->right);
            node->value = min->value;
            node->right = RemoveNode(node->right, min->value);
        }
        // 只有一个孩子
        else
        {
            TreeNode *ChildNode = node->left ? node->left : node->right;
            delete node;
            node = ChildNode;
        }
    }
    
    if(LRDvtion(node) > 1)
    {
        // 左左失衡
        if(LRDvtion(node->left) > 0)
        {
            node = RotateRight(node);
        }
        // 左右失衡
        else
        {
            node = RotateLeftRight(node);
        }
    }

    if(LRDvtion(node) < -1)
    {
        // 右右失衡
        if(LRDvtion(node->right) < 0)
        {
            node = RotateLeft(node);
        }
        // 右左旋
        else
        {
            node = RotateRightLeft(node);
        }
    }
    return node;
}

// 获取一棵树中的最小值点
BinaryTree::TreeNode *BinaryTree::GetMinNode(TreeNode *node)
{
    TreeNode *MinNode = node;
    while(MinNode->left != nullptr)
        MinNode = MinNode->left;
    return MinNode;
}

// 右旋
BinaryTree::TreeNode *BinaryTree::RotateRight(TreeNode *node)
{
    TreeNode *t = node->left;
    node->left = t->right;
    t->right = node;
    // 返回新的根
    return t;
}

// 左旋
BinaryTree::TreeNode *BinaryTree::RotateLeft(TreeNode *node)
{
    TreeNode *t = node->right;
    node->right = t->left;
    t->left = node;
    return t;
}

// 左右旋
BinaryTree::TreeNode *BinaryTree::RotateLeftRight(TreeNode *node)
{
    // 左子树左旋
    node->left = RotateLeft(node->left);
    // 整棵树右旋
    return RotateRight(node);
}

// 右左旋
BinaryTree::TreeNode *BinaryTree::RotateRightLeft(TreeNode *node)
{
    // 右子树右旋
    node->right = RotateRight(node->right);
    // 整棵树左旋
    return RotateLeft(node);
}

// 获取树的高度
int BinaryTree::GetNodeHeight(TreeNode *node)
{
    if(node == nullptr)
        return 0;
    int leftHeight = GetNodeHeight(node->left);
    int rightHeight = GetNodeHeight(node->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; 
}

// 左右子树高度差
int BinaryTree::LRDvtion(TreeNode *node)
{
    if(node == nullptr)
        return 0;
    return GetNodeHeight(node->left) - GetNodeHeight(node->right);
}
